package sort;

import java.util.Arrays;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName QuickSort.java
 * @Description TODO  https://blog.csdn.net/weixin_42437295/article/details/90771962   https://blog.csdn.net/qq_40595682/article/details/102146917
 * @createTime 2020年09月21日 20:55:00
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {1, 12, 3, 13, 14, 2, 44, 4, 56, 7};
		sortArray(arr);
		System.out.println(Arrays.toString(arr));
	}

	private static void sortArray(int[] arr) {
		doSort(arr,0,arr.length-1);
	}

	private static void doSort(int[] arr, int start, int end) {
		if (start>end){
			return;
		}
		int i=start,j=end,temp=arr[start],t;
		while (i<j){
			//右边，依次往左递减，找到比末尾位置大的
			while (temp<=arr[j]&&i<j){
				j--;
			}
			//左边，依次往右递增,找到比起始位置小的。
			while (temp>=arr[i]&&i<j){
				i++;
			}
			t=arr[i];
			arr[j]=arr[i];
			arr[i]=t;
		}
		//吧i放在最小的位置，跟i交换位子，此时的i位置的比temp小，所以交换i跟temp位置
		arr[start] = arr[i];
		arr[i] = temp;
		//循环左边
		doSort(arr, start, j - 1);
		//循环右边
		doSort(arr, j + 1, end);
	}




	/*private static void sortArray(int[] arr) {
		doSort(arr, 0, arr.length - 1);
	}

	private static void doSort(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		int i = start, j = end, temp = arr[start], t;
		while (i < j) {
			// 先看右边，依次往左递减，找到比末尾位置大的
			while (temp <= arr[j] && i < j) {
				j--;
			}
			// 再看左边，依次往右递增,找到比起始位置小的。
			while (temp >= arr[i] && i < j) {
				i++;
			}
			//交换位置i跟j的位置，因为j位置的比temp小，i位置的比temp大，所以吧i跟j交换
			t = arr[j];
			arr[j] = arr[i];
			arr[i] = t;
		}
		//吧i放在最小的位置，跟i交换位子，此时的i位置的比temp小，所以交换i跟temp位置
		arr[start] = arr[i];
		arr[i] = temp;
		//循环左边
		doSort(arr, start, j - 1);
		//循环右边
		doSort(arr, j + 1, end);
	}*/
}
